/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann Tübingen, Germany 
 * Niko Schenk Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package collectors.impl.visitors;

import collectors.api.Collector1;
import util.Interval;
import saphre.core.Store;
import saphre.core.SuffixArray;
import util.sorting.Multiset;

/**
 * A class that serves as the basis for several programs in the 'examples'
 * directory. Provides a kind of callback approach, so the programmer only needs
 * to be concerned with what information is to be gathered during the traversal,
 * and can ignore the mechanics of the traversal itself.
 * 
 * @author Dale Gerdemann
 */
public class PostOrderTraversal {

    Store store;
    SuffixArray sa;
    Collector1 collect;
    Interval top;
    SuffixArray pa;
    // The following is used to show lcp-interval tree as in fig 7 of
    // Kim et al. See PrintTraversal2.java.
    public static int pseudoDepth = 0;
    public static int lcpStart = 0;

    /**
     * 
     * @param store
     * @param sa
     * @param collect
     * @param top 
     */
    public PostOrderTraversal(Store store, SuffixArray sa, Collector1 collect,
            Interval top) {
        this.store = store;
        this.sa = sa;
        this.collect = collect;
        this.top = top;
    }

    /*
     * 
     */
    public Collector1 traverse() {
        traverse(top, -1, 0);
        return collect;
    }

    /*
     * 
     */
    private Multiset[] traverse(Interval inter, int lcp, int depth) {
        if (inter.trivial()) {
            Multiset[] result = new Multiset[2];

            Multiset docDist = new Multiset();
            int loc = sa.suftab[inter.lb()];
            int docID = store.docNum(loc);
            docDist.incr(docID);
            result[0] = docDist;

            // System.out.println("Trivial: "+store.toString(loc,loc+lcp));

            Multiset leftContext = new Multiset();
            leftContext.incr(store.text[loc - 1]);
            result[1] = leftContext;
            collect.addTrivial(inter, lcp, depth, docDist, leftContext);
            return result;
        } else {
            int mid = sa.cldtab[inter.lb()];
            if (mid <= inter.lb() || mid > inter.rb()) {
                mid = sa.cldtab[inter.rb()];
            }
            Interval left = new Interval(inter.lb(), mid - 1);
            Interval right = new Interval(mid, inter.rb());
            boolean lcpInter = false;
            int parentLcp = lcp;
            if (lcp < sa.lcptab[mid]) {
                lcp = sa.lcptab[mid];
                lcpInter = true;
            }

            collect.preAdd(inter, parentLcp, lcp, depth);
            Multiset[] ps1 = traverse(left, lcp,
                    depth + (lcpInter ? 1 : pseudoDepth));
            Multiset[] ps2 = traverse(right, lcp,
                    depth + (lcpInter ? 1 : pseudoDepth));
            if (lcp > lcpStart) {
                join(ps1, ps2);
                if (lcpInter) {
                    collect.add(inter, lcp, depth, ps1[0], ps1[1]);
                }
            }
            return ps1;
        }
    }

    /*
     * 
     */
    private void join(Multiset[] a, Multiset[] b) {
        for (int i = 0; i < a.length; i++) {
            a[i].join(b[i]);
        }
    }
}
